package List;

/**
 * 链表相交
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 题目数据 保证 整个链式结构中不存在环。
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 */
public class getIntersectionNode {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public class Solution {

        /**
         * 二刷
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;

            ListNode a = headA;
            ListNode b = headB;

            while (a != b) {
                a = (a != null) ? a.next : headB;
                b = (b != null) ? b.next : headA;
            }
            return a;
        }

        /**
         * 一刷
         */
        public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
            int lengthA = 0;
            int lengthB = 0;
            while (headA != null) {
                lengthA++;
                headA = headA.next;
            }
            while (headB != null) {
                lengthB++;
                headB = headB.next;
            }
            int cut = lengthA - lengthB;
            while (cut > 0) {
                headA = headA.next;
                cut--;
            }
            while (cut < 0) {
                headB = headB.next;
                cut++;
            }
            while (headA!=null&&headB!=null) {
                if (headA.val == headB.val) {
                    return headA;
                }
                headA = headA.next;
                headB = headB.next;
            }
            return null;

        }
    }


    /**
     * hot100一刷
     * hot100二刷
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while (headA != headB) {
            headA = headA == null ? b : headA.next;
            headB = headB == null ? a : headB.next;
        }
        return headA;
    }


}
